package cn.bouncyslime.dataStructures.tree.traverseBinaryTree;

import cn.bouncyslime.dataStructures.tree.node.Node;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author bouncyslime
 * @date 2021/1/17
 */
public class BinaryTreeTraversing_LRD implements BinaryTreeTraversing{
    /**
     * 递归后序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseRecursively(Node<T> root){
        if (root != null) {
            if (root.getLeft() != null){
                traverseRecursively(root.getLeft());
            }
            if (root.getRight() != null) {
                traverseRecursively(root.getRight());
            }
            System.out.print(root.getData() + " | ");
        }
    }

    /**
     * 利用栈迭代后序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseIteratively(Node<T> root){
//        Deque<Node<T>> stack = new LinkedList<>();
//        Node<T> node = root;
//        while(node != null || !stack.isEmpty()){
//            if(node != null){
//                stack.push(node);
//                node = node.getLeft();
//            }else{
//                node = stack.pop();
//                System.out.print(node.getData() + " | ");
//                node = node.getRight();
//            }
//        }
    }

    /**
     * 利用栈迭代后序遍历二叉树
     * @param root 二叉树根结点
     */
    public <T> void traverseIteratively2(Node<T> root) {
//        Deque<Node<T>> stack = new LinkedList<>();
//        Node<T> node = root;
//        stack.push(node);
//        while (!stack.isEmpty()){
//            while ((node = stack.peek()) != null) {
//                stack.push(node.getLeft());
//            }
//            stack.pop();
//            if (!stack.isEmpty()){
//                node = stack.pop();
//                stack.push(node.getRight());
//            }
//        }
    }

    public static void main(String[] args) {
        BinaryTreeTraversing binaryTreeTraversing = new BinaryTreeTraversing_LRD();

        String[] array = {"1", "2", "3", "4", "5", null, null, null, null, "6", "7"};
        Node<String> root = BinaryTreeUtils.createBinaryTreeFromArray(array);
        binaryTreeTraversing.traverseRecursively(root);
        System.out.println();

        Integer[] integers = {1, 2, 3, 4, 5, null, null, null, null, 6, 7};
        Node<Integer> integerRoot = BinaryTreeUtils.createBinaryTreeFromArray(integers);
        binaryTreeTraversing.traverseRecursively(integerRoot);
        System.out.println();

        binaryTreeTraversing.traverseIteratively(integerRoot);
        System.out.println();

        binaryTreeTraversing.traverseIteratively2(integerRoot);
    }
}
